CodeForces978C Letters

There are  dormitories in Berland State University, they are numbered with integers from  to . Each dormitory consists of rooms, there are  rooms in -th dormitory. The rooms in -th dormitory are numbered from  to .

A postman delivers letters. Sometimes there is no specific dormitory and room number in it on an envelope. Instead of it only a room number among all rooms of all dormitories is written on an envelope. In this case, assume that all the rooms are numbered from  to  and the rooms of the first dormitory go first, the rooms of the second dormitory go after them and so on.

For example, in case ,  and  an envelope can have any integer from to  written on it. If the number  is written on an envelope, it means that the letter should be delivered to the room number  of the second dormitory.

For each of  letters by the room number among all  dormitories, determine the particular dormitory and the room number in a dormitory where this letter should be delivered.

Input
The first line contains two integers  and   — the number of dormitories and the number of letters.

The second line contains a sequence  , where  equals to the number of rooms in the -th dormitory. The third line contains a sequence  , where  equals to the room number (among all rooms of all dormitories) for the -th letter. All  are given in increasing order.

Output
Print  lines. For each letter print two integers  and  — the dormitory number  and the room number  in this dormitory  to deliver the letter.

Examples
Input
3 6
10 15 12
1 9 12 23 26 37
Output
1 1
1 9
2 2
2 13
3 1
3 12
Input
2 3
5 10000000000
5 6 9999999999
Output
1 5
2 1
2 9999999994
Note
In the first example letters should be delivered in the following order:

the first letter in room  of the first dormitory
the second letter in room  of the first dormitory
the third letter in room  of the second dormitory
the fourth letter in room  of the second dormitory
the fifth letter in room  of the third dormitory
the sixth letter in room  of the third dormitory

解析：

题意: 查询m个数分别在一个有n个元素的递增序列中的相对位置。

两种解法：
暴力解法为两层嵌套循环，时间复杂度为O(m×n)；
二分法查找，时间复杂度为O(m×log2n)

#include <stdio.h>
#define MAXN 2048 //定义一个数组的大小

// 暴力求解
int letters(int* a, int* b, int n, int m)
{
    int i, j, t, sum=0;
    
    for(j = 0; j < m; j++)
    {
        sum = 0;
        for(i = 0; i < n; i++)
        {
            sum += a[i];
            if(b[j] <= sum)
            {
                t = sum - a[i];
                printf("%d %d\n", i+1, b[j] - t);
                break;
            }
        }
    }
    
    return 0;
}

// 二分法
int binary_letters(int* a, int* b, int n, int m)
{
    int sum[MAXN] = {0};
    int i, j, r, l, mid;
    
    sum[0] = a[0];

    // 构建ai序列
    for(i = 1; i < n; i++)
        sum[i] = sum[i-1] + a[i];

    for(j = 0; j < m; j++)
    {
        if(b[j] > sum[i-1])
        {
            printf("%d index out of bounds.\n", b[j]);
            continue;
        }
        
        for(r = n - 1, l = 0; r - l > 1; )
        {
            mid = (r + l) / 2;
            if(b[j] > sum[mid])
                l = mid;
            else
                r = mid;
        }
        
        if(b[j] > sum[l])
            printf("%d %d\n", l+2, b[j]-sum[l]);
        else
            printf("%d %d\n", l+1, b[j]);
    }
    
    return 0;
}

int main()
{
    int a[] = {10, 15, 12, 12, 12};
    int b[] = {1, 9, 12, 23, 26, 37, 50, 62};

    int n = sizeof(a) / sizeof(int);
    int m = sizeof(b) / sizeof(int);

    letters(a, b, n, m);
    printf("================\n");
    binary_letters(a, b, n, m);
    
    return 0;
}

out put

1 1
1 9
2 2
2 13
3 1
3 12
5 1
================
1 1
1 9
2 2
2 13
3 1
3 12
5 1
62 index out of bounds.